/*
实验3-1 在一个数组中实现两个栈
分数 20
作者 陈越
单位 浙江大学

试在一个长度为 n 的数组中实现两个栈，使得二者在元素的总数目为 n 之前都不溢出，并保证 Push 和 TopPop 操作的时间代价为 O(1)。
函数接口定义：

void InitStack(Stack stack, int n);
bool Push (Stack stack, int tag, SElemSet x);
bool IsEmpty(Stack stack, int tag);
SElemSet TopPop (Stack stack, int tag);

其中 Stack 数据类型的定义如下：

typedef int Position;    // 整型下标，表示元素的位置 
typedef struct StackNode *Stack;
struct StackNode {
    int capacity;        // 两个顺序栈的总容量 
    Position top1, top2; // 两个顺序栈的栈顶指针 
    SElemSet *data;      // 存储数据的数组 
};

函数接口定义中，SElemSet 是用户定义的数据类型，例如 int、double 或者 char 等；n 是数组的长度，也就是两个栈的总容量；
tag 是栈的编号，为 1 时表示对 top1 所指的栈顶进行操作，为 2 时表示对 top2 所指的栈顶进行操作。

InitStack 需要将 stack 进行初始化，即将 n 赋值给 capacity，为 n 个元素声明数组空间，并且定义两个栈顶指针的初值。

Push 函数将 x 插入第 tag 个栈。注意：如果栈已满，Push 函数必须输出 Stack Full 并且返回 false。成功插入则返回 true。

IsEmpty 函数判断第 tag 个栈是否为空，空则返回 true，否则返回 false。

TopPop 函数是标准栈函数 Top 和 Pop 的组合，需要将第 tag 个栈的栈顶元素从该栈中移除，并返回其值。
如果第 tag 个栈是空的，则 Pop 函数必须返回 ERROR。

输入样例：

5
Push 1 1
Pop 2
Push 2 11
Push 1 2
Push 2 12
Pop 1
Push 2 13
Push 2 14
Push 1 3
Pop 2
End

输出样例：

Stack 2 is Empty
Stack Full
3 is not in Stack 1
Pop from Stack 1: 1
Pop from Stack 2: 13 12 11
*/

#include <stdio.h>
#include <stdlib.h>

#define ERROR (1e7)
typedef enum { push, pop, end } Operation; /* 操作类型 */
typedef enum { false, true } bool;
typedef int SElemSet;     /* 栈元素类型定义为整型 */
typedef int Position;     /* 整型下标，表示元素的位置 */
typedef struct StackNode *Stack;
struct StackNode {
    int capacity;         /* 两个顺序栈的总容量 */
    Position top1, top2;  /* 两个顺序栈的栈顶指针 */
    SElemSet *data;       /* 存储数据的数组 */
};

void InitStack (Stack stack, int n);
bool Push (Stack stack, int tag, SElemSet x);
bool IsEmpty(Stack stack, int tag);
SElemSet TopPop (Stack stack, int tag);

Operation GetOp ()
{ /* 判断输入的操作类型 */
    char op[5]; /* 操作最长4个字符 */
    Operation ret; 
    
    scanf(" %s ", op);
    switch (op[1]) { /* 用第2个字母区分操作 */
        case 'u': ret = push; break;
        case 'o': ret = pop; break;
        case 'n': ret = end; break;
        default: break;
    }
    return ret;
}

void PrintStack (Stack stack, int tag)
{
    printf("Pop from Stack %d:", tag);
    while (!IsEmpty(stack, tag)) {
        printf(" %d", TopPop(stack, tag));
    }
    printf("\n");
}

int main(void)
{
    int n, tag, x;
    Stack stack;
    bool done;
    stack = (Stack)malloc(sizeof(struct StackNode));
    scanf("%d", &n);
    InitStack(stack, n); /* 初始化栈空间 */
    done = false; /* 初始化结束标识 */
    while ( done == false ) {
        switch( GetOp() ) {
            case push: /* 执行入栈操作 */
                scanf("%d %d\n", &tag, &x);
                if (Push(stack, tag, x) == false) {
                    printf("%d is not in Stack %d\n", x, tag);
                }
                break;
            case pop: /* 执行出栈操作 */
                scanf("%d\n", &tag);
                x = TopPop(stack, tag);
                if (x == ERROR) {
                    printf("Stack %d is Empty\n", tag);
                }
                break;
            case end: /* 输入结束，打印栈元素 */
                PrintStack(stack, 1);
                PrintStack(stack, 2);
                done = true;
                break;
            default: break;
        }
    }
    return 0;
}
/* 你的代码将被嵌在这里 */

void InitStack (Stack stack, int n) {
    stack->capacity = n;
    stack->top1 = -1;
    stack->top2 = n;
    stack->data = (SElemSet *)malloc(n * sizeof(SElemSet));
}

bool Push (Stack stack, int tag, SElemSet x) {
    if (stack->top1 + 1 == stack->top2) {
        printf("Stack Full\n");
        return false;
    }
    if (tag == 1) {
        stack->data[++stack->top1] = x;
    } else {
        stack->data[--stack->top2] = x;
    }
    return true;
}

bool IsEmpty(Stack stack, int tag) {
    if (tag == 1) {
        return stack->top1 == -1;
    } else {
        return stack->top2 == stack->capacity;
    }
}

SElemSet TopPop (Stack stack, int tag) {
    if (IsEmpty(stack, tag)) {
        return ERROR;
    }
    if (tag == 1) {
        return stack->data[stack->top1--];
    } else {
        return stack->data[stack->top2++];
    }
}
